Транзакции - 2

Максимальная оценка за эту задачу — 40 баллов.

В этой задаче $n = 10000$. Условие задачи и форматы ввода и вывода полностью совпадают с предыдущей задачей, однако в этой задаче вам необходимо сдать на проверку текстовый файл с ответом на конкретный тест, который вы должны сгенерировать на своем компьютере. Скачать файл со входными данными для этой задачи вы можете нажав на ссылку "Скачать условие задачи" внизу этой страницы (после раздела "Система оценивания").

Во время тура ответ будет проверяться только на соответствие формату, проверка с выставлением баллов будет осуществляться после окончания тура. Статус OK и 0 баллов во время тура означает, что сданный вами файл соответствует формату и будет проверен после тура, в случае других статусов файл не соответствует формату и вам следует проверить и исправить его.

Для ускорения работы файловой системы на сервере необходимо накапливать операции ввода-вывода (транзакции) в буфере, а затем выполнять их.

Всего в буфере накоплено $n$ транзакций, пронумерованных от $1$ до $n$. Память сервера состоит из $m$ участков, пронумерованных от $1$ до $m$. Для каждой транзакции известно множество участков памяти, из которых данная транзакция производит чтение, и множество участков памяти, в которые она производит запись. Для $i$-й транзакции обозначим эти множества как $RS_i$ и $WS_i$.

Из заданного множества транзакций нужно выбрать некоторое подмножество и упорядочить транзакции внутри него.

Пусть было выбрано упорядоченное подмножество (последовательность) из $k$ транзакций с номерами $p_1, p_2, \ldots, p_k$. В выбранной последовательности транзакций не должно быть конфликтов. Конфликтом называется пара транзакций, в которой более ранняя транзакция записывает данные в область памяти, из которого затем читает другая транзакция. Более формально, транзакции $p_i$ и $p_j$, где $i < j$, конфликтуют, если существует такой участок памяти $l$, что $l \in WS_{p_i}$ и $l \in RS_{p_j}$.

По данному множеству транзакций вам нужно выбрать из него последовательность транзакций наибольшей возможной длины, не содержащей конфликтов. Вам не требуется находить оптимальное решение в данной задаче. Ваше решение получит количество баллов, пропорциональное длине найденной вами последовательности транзакций.